#include "iostream"
#include "cstdio"
#include "map"
#include "queue"
#include "vector"
#include "string.h"
#include "cstdlib"
#include "algorithm"
#include "set"
#include "ctime"
#include "cmath"
#include "BigNumber.h"
#include "BigPrime.h"
#include "RSAKey.h"
#include "exgcd.h"


#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif

using namespace std;
typedef long long LL;
typedef unsigned char uc;



class RSA
{
public:
    exgcdSolution exgcd(BigInteger a, BigInteger phiN, exgcdSolution sol);
    RSAFinalKey generateRandomKey(BigInteger phiN, short length);
    RSAFinalKey generateChosenKey(BigInteger phiN, BigInteger e);

private:

};
class K{
    public:
    BigInteger e,d;
};


BigInteger x1 = 0;
BigInteger gcd(BigInteger a,BigInteger b){
    if (b==numZero){
        return a;
    }
    else{
        return gcd(b,a%b);
    }
}
exgcdSolution RSA::exgcd(BigInteger a, BigInteger phiN, exgcdSolution sol)
{
    if (numZero==phiN) {
        exgcdSolution p;
        p.x = numOne;
        p.y = numZero;
        return p;
    }
    sol = exgcd(phiN, a%phiN, sol);
    
    
    
    x1 = sol.x;
    sol.x = sol.y;
    sol.y = x1-((a/phiN)*(sol.y));
    return sol;
}
RSAFinalKey RSA::generateRandomKey(BigInteger phiN, short length) {
        RSAFinalKey rsaKey;
        rsaKey.d = numZero;
        Prime prime;
        K keys;
        
            
            
            keys.e =prime.generateSingle(length);
            while (!(numOne==gcd(phiN, keys.e))) {
                keys.e = keys.e + numOne;
            }
            exgcdSolution Pkey;
            Pkey = (*this).exgcd(keys.e, phiN, Pkey);
            rsaKey.e = keys.e;
            rsaKey.d = Pkey.x;
           if  (rsaKey.d.isNegative()) {
               rsaKey.d+=phiN;
        }
        return rsaKey;
    }
RSAFinalKey RSA::generateChosenKey(BigInteger phiN, BigInteger e) {
        RSAFinalKey rsaKey;
        rsaKey.d = numZero;
        Prime prime;
        K keys;
        if (!(numOne==gcd(phiN, e))) {
            cout<<"e与phiN 不互素！";
            exit(1);
        }
        keys.e = e;
        while (rsaKey.d.isNegative()) {
            
            
            exgcdSolution Pkey;
            Pkey = (*this).exgcd(keys.e, phiN, Pkey);
            rsaKey.e = keys.e;
            rsaKey.d = Pkey.x;
        }
        return rsaKey;
    }